def dfs(grid,visited,i,j):
    m,n=len(grid),len(grid[0])
    visited[i][j]=True 
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
        newi,newj=i+d[0],j+d[1]
        if newi>=0 and newi<m and newj>=0 and newj<n and grid[newi][newj]=="1" and (not visited[newi][newj]):
            dfs(grid,visited,newi,newj)

def solve(grid):
    m,n=len(grid),len(grid[0])
    visited=[[False]*n for _ in range(m)]
    ans=0
    for i in range(m):
        for j in range(n):
            if grid[i][j]=="1" and (not visited[i][j]):
                #print(visited)
                ans+=1
                dfs(grid,visited,i,j)
    return ans 

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(solve(grid))
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(solve(grid))